Micron Document
<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Adjazenzgraph</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Adjazenzgraph"> <link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Adjazenzgraph rootpage-Adjazenzgraph skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Adjazenzgraph</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Ein <b>Adjazenzgraph</b> ist ein Konzept der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a>, das jeder <a href="Matrix_(Mathematik)" title="Matrix (Mathematik)">Matrix</a> einen <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> zuordnet. Damit wird eine Verbindung von <a href="Lineare_Algebra" title="Lineare Algebra">Linearer Algebra</a> und Graphentheorie hergestellt, die es erlaubt, Begriffe und Lösungskonzepte zu übertragen.
</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>Sei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\in \mathbb {R} ^{n\times n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>×<!-- × --></mo>
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A\in \mathbb {R} ^{n\times n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ebb63eca276c71633e0939f5c5d4ef4bfc565518.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.745ex; height:2.343ex;" alt="{\displaystyle A\in \mathbb {R} ^{n\times n}}" loading="lazy"></span> eine Matrix mit reellen Einträgen. Dann ist der Adjazenzgraph ohne Kantengewichte <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{A}=(V,E)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>G</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>A</mi>
</mrow>
</msub>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mi>V</mi>
<mo>,</mo>
<mi>E</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle G_{A}=(V,E)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/90335181007d256a8d1c0371c37538b0b97a0275.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.796ex; height:2.843ex;" alt="{\displaystyle G_{A}=(V,E)}" loading="lazy"></span> von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> definiert als
</p>
<ul><li>Die Knotenmenge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V=\{1,\ldots ,n\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>V</mi>
<mo>=</mo>
<mo fence="false" stretchy="false">{</mo>
<mn>1</mn>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mi>n</mi>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V=\{1,\ldots ,n\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ef7fcbd1a991047ef106e0967b6a9587ac72ef9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.946ex; height:2.843ex;" alt="{\displaystyle V=\{1,\ldots ,n\}}" loading="lazy"></span></li>
<li>Die Kantenmenge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>E</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle E}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span>. Dabei ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)\in E}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo stretchy="false">)</mo>
<mo>∈<!-- ∈ --></mo>
<mi>E</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (i,j)\in E}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce48c5e7da04eca1eca6af5f79f823ad134edb24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.22ex; height:2.843ex;" alt="{\displaystyle (i,j)\in E}" loading="lazy"></span> genau dann wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i,j}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a_{i,j}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4bb5a346f58c6568306a02596dd318d1b7e6b2c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.164ex; height:2.343ex;" alt="{\displaystyle a_{i,j}}" loading="lazy"></span> von 0 verschieden ist</li></ul>
<p>Will man einen gewichteten Adjazenzgraph erstellen, so erhält die Kante <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (i,j)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ef21910f980c6fca2b15bee102a7a0d861ed712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.604ex; height:2.843ex;" alt="{\displaystyle (i,j)}" loading="lazy"></span> das Gewicht <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i,j}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a_{i,j}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4bb5a346f58c6568306a02596dd318d1b7e6b2c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.164ex; height:2.343ex;" alt="{\displaystyle a_{i,j}}" loading="lazy"></span>, falls dieses von 0 verschieden ist.
</p><p>Diese Definition entspricht der Interpretation der Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> als eine <a href="Adjazenzmatrix" title="Adjazenzmatrix">Adjazenzmatrix</a> und der Rekonstruktion des Graphen aus dieser.
</p>
<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>
<p>Wie auch bei der Adjazenzmatrix schlagen sich einige Eigenschaften der Matrix im Adjazenzgraph wieder:
</p>
<ul><li>Der Adjazenzgraph ist ungerichtet genau dann wenn die Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> <a href="Symmetrische_Matrix" title="Symmetrische Matrix">symmetrisch</a> ist.</li>
<li>Der Adjazenzgraph ist schleifenfrei genau dann wenn alle Diagonaleinträge von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> gleich 0 sind.</li>
<li>Der Adjazenzgraph ist genau dann <a href="Zusammenhang_(Graphentheorie)" title="Zusammenhang (Graphentheorie)">stark zusammenhängend</a>, wenn die Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> irreduzibel ist.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Verwendung">Verwendung</h2></div>
<p>Wie auch die Adjazenzmatrix schlägt der Adjazenzgraph eine Verbindung zwischen Linearer Algebra und Graphentheorie und erlaubt somit, Lösungskonzepte beider Themen zu verbinden. Beispiel hierfür ist die Irreduzibilität von Matrizen. Diese lässt sich mit Mitteln der Linearen Algebra nur schwer überprüfen. Erstellt man den Adjazenzgraphen und überprüft diesen auf starken Zusammenhang, so ist dies äquivalent zur Überprüfung der Irreduzibilität der Matrix.
Außerdem bieten sich Adjazenzgraphen zur Veranschaulichung von <a href="Markow-Kette" title="Markow-Kette">Markow-Ketten</a> an, da jeder <a href="%C3%9Cbergangsgraph" title="Übergangsgraph">Übergangsgraph</a> Adjazenzgraph einer <a href="%C3%9Cbergangsmatrix" title="Übergangsmatrix">zeilenstochastischen Matrix</a> ist.
</p>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li><a href="Peter_Knabner" title="Peter Knabner">Peter Knabner</a>, <a href="Wolf_Barth_(Mathematiker)" title="Wolf Barth (Mathematiker)">Wolf Barth</a>: <cite style="font-style:italic">Lineare Algebra</cite>. Grundlagen und Anwendungen (=&nbsp;<cite style="font-style:italic">Springer-Lehrbuch</cite>). Springer, Berlin 2012, ISBN 978-3-642-32185-6.<span class="Z3988" title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rfr_id=info:sid/de.wikipedia.org:Adjazenzgraph&amp;rft.au=Peter+Knabner%2C+Wolf+Barth&amp;rft.btitle=Lineare+Algebra&amp;rft.date=2012&amp;rft.genre=book&amp;rft.isbn=9783642321856&amp;rft.place=Berlin&amp;rft.pub=Springer&amp;rft.series=Springer-Lehrbuch" style="display:none">&nbsp;</span></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2021-07-13" href="https://de.wikipedia.org/wiki/?title=Adjazenzgraph&amp;oldid=213828987">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>

</body></html>